Добро пожаловать на занятие 3 курса Концепции искусственного интеллекта (PolyU COMP5511). На этом занятии мы переходим от поиска пути одним агентом к состязательному поиску, где агенты действуют в конкурентной многоагентной среде. Мы также рассмотрим задачи удовлетворения ограничений (CSP)— парадигму, в которой цель состоит в поиске состояния, удовлетворяющего заданному набору ограничений, а не пути.
Ключевые концепции
- Состязательный поиск: Рассматривает такие алгоритмы, как минимакс и альфа-бета отсечение для принятия рациональных решений против разумного противника.
- Поиск по дереву методом Монте-Карло (MCTS): Исследует вероятностное принятие решений и лежит в основе современных игровых ИИ, таких как AlphaGo.
- Удовлетворение ограничений: Моделирует задачи через переменные, домены и ограничения, решаемые с помощью поиска с возвратом и локального поиска.
Анализ сложности
В состязательных средах сложность пространства поиска обычно определяется коэффициентом ветвления игры
Предупреждение о смене парадигмы
В отличие от стандартного поиска (например, A* или BFS), где среда статична, состязательному поиску предполагает, что среда (противник) активно пытается минимизировать ваш успех. В задачах CSPпорядок действий менее важен, чем корректность итогового назначения.
Концептуальный псевдокод: типы агентов
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).